﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCodeTopic
{
    class Program
    {
        static void Main(string[] args)
        {
            //Console.WriteLine(LongestPalindrome("cbabad"));

            //Console.WriteLine(Convert("LEETCODEISHIRING", 4));

            //Console.WriteLine(Reverse(123456));

            //Console.WriteLine(maxArea(new int[] { 10, 1, 8, 6, 2, 5, 4, 8, 3, 7, 9 }));

            //Console.WriteLine(string.Join("\r\n", generateParenthesis(3).ToArray()));

            Console.WriteLine(KMP("abcdedg", "edg"));
        }

        /// <summary>
        /// 中心扩展算法
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string LongestPalindrome(string s)
        {
            if (s == "")
                return s;
            int len = s.Length;
            int maxlen = 1;
            int start = 0;

            for (int i = 0; i < len; i++)
            {
                int j = i - 1, k = i + 1;
                while (j >= 0 && k < len && s[j] == s[k])
                {
                    if (k - j + 1 > maxlen)
                    {
                        maxlen = k - j + 1;
                        start = j;
                    }
                    j--;
                    k++;
                }
            }

            for (int i = 0; i < len; i++)
            {
                int j = i, k = i + 1;
                while (j >= 0 && k < len && s[j] == s[k])
                {
                    if (k - j + 1 > maxlen)
                    {
                        maxlen = k - j + 1;
                        start = j;
                    }
                    j--;
                    k++;
                }
            }
            return s.Substring(start, maxlen);
        }

        /// <summary>
        /// Z型字符变换
        /// </summary>
        /// <param name="s"></param>
        /// <param name="numRows"></param>
        /// <returns></returns>
        public static string Convert(string s, int numRows)
        {
            if (numRows == 1)
                return s;

            List<StringBuilder> rows = new List<StringBuilder>();
            for (int i = 0; i < Math.Min(numRows, s.Length); i++)
                rows.Add(new StringBuilder());

            int curRow = 0;
            bool goingDown = false;
            foreach (char c in s.ToCharArray())
            {
                rows[curRow].Append(c);
                if (curRow == 0 || curRow == numRows - 1)
                    goingDown = !goingDown;
                curRow += goingDown ? 1 : -1;
            }

            StringBuilder ret = new StringBuilder();
            foreach (StringBuilder row in rows)
                ret.Append(row);

            return ret.ToString();
        }

        /// <summary>
        /// 整数类型翻转
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public static int Reverse(int x)
        {
            int rev = 0;
            while (x != 0)
            {
                int pop = x % 10;
                x /= 10;
                if (rev > int.MaxValue / 10 || (rev == int.MaxValue / 10 && pop > 7))
                    return 0;
                if (rev < int.MinValue / 10 || (rev == int.MinValue / 10 && pop < -8))
                    return 0;
                rev = rev * 10 + pop;
            }
            return rev;
        }

        /// <summary>
        /// 盛最多水的容器
        /// </summary>
        /// <param name="height"></param>
        /// <returns></returns>
        public static int maxArea(int[] height)
        {
            int maxarea = 0, l = 0, r = height.Length - 1;
            while (l < r)
            {
                maxarea = Math.Max(maxarea, Math.Min(height[l], height[r]) * (r - l));
                if (height[l] < height[r])
                    l++;
                else
                    r--;
            }
            return maxarea;

        }

        #region 括号生成

        public static List<string> generateParenthesis(int n)
        {
            List<string> combinations = new List<string>();
            generateAll(new char[2 * n], 0, combinations);
            return combinations;

        }

        public static void generateAll(char[] current, int pos, List<string> result)
        {
            if (pos == current.Length)
            {
                if (valid(current))
                    result.Add(new string(current));
            }
            else
            {
                current[pos] = '(';
                generateAll(current, pos + 1, result);
                current[pos] = ')';
                generateAll(current, pos + 1, result);
            }
        }

        public static bool valid(char[] current)
        {
            int balance = 0;
            foreach (char c in current)
            {
                if (c == '(')
                    balance++;
                else
                    balance--;
                if (balance < 0)
                    return false;
            }
            return (balance == 0);
        }
        #endregion

        /// <summary>
        /// 通过KPM算法 模拟IndexOf 不过只是返回布尔类型 找到true, 找不到false
        /// </summary>
        /// <param name="haystack"></param>
        /// <param name="needle"></param>
        /// <returns></returns>
        public static int KMP(string haystack, string needle)
        {
            int strLen = haystack.Length, 
                needleLen = needle.Length;

            if (needleLen == 0) return 0;
            if (strLen == 0) return -1;

            // 构建状态机
            int[][] FSM = new int[needleLen][];
            for (int ii = 0; ii < needleLen; ii++)
            {
                FSM[ii] = new int[256];
            }
            int X = 0, match = 0;
            for (int i = 0; i < needleLen; i++)
            {
                match = needle.ToCharArray()[i];
                for (int j = 0; j < 256; j++)
                {
                    // 当前状态 + 匹配失败字符 = 孪生词缀状态 + 匹配字符
                    FSM[i][j] = FSM[X][j];
                }
                FSM[i][match] = i + 1;
                if (i > 0)
                {
                    // 下一孪生前缀状态 = X + match
                    X = FSM[X][match];
                }
            }
            // 匹配子串
            int state = 0;
            for (int i = 0; i < strLen; i++)
            {
                state = FSM[state][haystack.ToCharArray()[i]];
                if (state == needleLen)
                {
                    return i - needleLen + 1;
                }
            }
            return -1;
        }
    }
}
